

//输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空
//（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
public class Solution {
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    //代码一
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null){
            return null;
        }
        int size1 = 0;
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while(cur1!= null){
            size1++;
            cur1 = cur1.next;
        }
        int size2 = 0;
        while(cur2 != null){
            size2++;
            cur2 = cur2.next;
        }
        if(size1 > size2){
            int num = size1 - size2;
            for(int i = 0; i < num; i++){
                pHead1 = pHead1.next;
            }
        }else{
            int num = size2 - size1;
            for(int i = 0; i < num; i++){
                pHead2 = pHead2.next;
            }
        }
        while(pHead1 != null && pHead2 != null){
            if(pHead1 == pHead2){
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }

    //代码二
    public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1, l2 = pHead2;
        while(l1 != l2){
            l1 = (l1==null)?pHead2:l1.next;
            l2 = (l2==null)?pHead1:l2.next;
            //对于指针 l1，如果它当前指向 null，说明已经遍历完了链表 1，此时将其重新指向链表 2 的头节点 pHead2；否则，将其移动到下一个节点 l1.next。
            //对于指针 l2，如果它当前指向 null，说明已经遍历完了链表 2，此时将其重新指向链表 1 的头节点 pHead1；否则，将其移动到下一个节点 l2.next
        }
        return l1;
    }
}
